/*
 * @Author: szx
 * @Date: 2021-11-13 12:32:18
 * @LastEditTime: 2021-11-13 12:52:12
 * @Description:
 * @FilePath: \leetcode\200-299\200\200.go
 */
package main

func numIslands(grid [][]byte) int {
	var num int
	var dfs func(int, int)
	dfs = func(i, j int) {
		if i >= len(grid) || i < 0 {
			return
		}
		if j >= len(grid[0]) || j < 0 {
			return
		}
		if grid[i][j] == '1' {
			grid[i][j] = '0'
			dfs(i+1, j)
			dfs(i, j+1)
			dfs(i-1, j)
			dfs(i, j-1)
		}
	}

	for i := 0; i < len(grid); i++ {
		for j := 0; j < len(grid[0]); j++ {
			if grid[i][j] == '1' {
				dfs(i, j)
				num++
			}
		}
	}
	return num
}

// 队列
// func numIslands(grid [][]byte) int {
// 	a := []int{1, 0, -1, 0}
// 	b := []int{0, 1, 0, -1}
// 	que := make([]int, 0)
// 	cnt := 0
// 	for i := 0; i < len(grid); i++ {
// 		for j := 0; j < len(grid[0]); j++ {
// 			if grid[i][j] == '1' {
// 				cnt++
// 				que = append(que, i, j)
// 				grid[i][j] = '0'
// 				for len(que) != 0 {
// 					tmp_i, tmp_j := que[0], que[1]
// 					que = que[2:]
// 					for m := 0; m < 4; m++ {
// 						mx := tmp_i + a[m]
// 						my := tmp_j + b[m]
// 						if mx >= 0 && mx < len(grid) && my >= 0 && my < len(grid[0]) && grid[mx][my] == '1' {
// 							grid[tmp_i][tmp_j] = '0'
// 							que = append(que, i, j)
// 						}
// 					}
// 				}
// 			}
// 		}
// 	}
// 	return cnt
// }
